package com.xtianzhuang.www.study2019.practice.leetcode.algorithm;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * @author xtian.zhuang
 * @date Mar 30, 2019
 */
public class Question3 {
	private static final String DEFAULT_WAY = "1";
	private static final String WAY_1 = "1";
	private static final String WAY_3 = "3";
	private static String[] testStrs = {"abcabcbb", "bbbbb", "pwwkew", "ab", "aab", "",
			"egrqmqxaspvlrarmetsephovokkxgjalprbbhadcpbnhbhvfaolpxamokwntfnewehzojeqzffigmfmovxdtzrhmpufwi"};

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		for (String str : testStrs) {
			System.out.println(lengthOfLongestSubstring(WAY_3, str));
		}
		long end = System.currentTimeMillis();
		System.out.println("耗时：" + (end - start) + "ms");
	}

	static int lengthOfLongestSubstring(String type, String s) {
		if (type.equals("1")) {
			return lengthOfLongestSubstring1(s);
		} else if (type.equals("3")) {
			return lengthOfLongestSubstring3(s);
		}
		return lengthOfLongestSubstring1(s);
	}

	/**
	 * 穷举，特别慢，但是能实现基本功能
	 * @param s
	 * @return
	 */
	static int lengthOfLongestSubstring1(String s) {
		if (s == null || s.equals("")) {
			return 0;
		}
		String[] strs = s.split("");
		int max = 1;
		for (int i = 0; i < strs.length - 1; i++) {
			for (int j = i + 1; j < strs.length; j++) {
				String item = s.substring(i, j + 1);
				Set<String> set = new HashSet<>();
				for (int k = 0; k < item.length(); k++) {
					char tString = item.charAt(k);
					set.add(String.valueOf(tString));
				}
				if (s.substring(i, j + 1).length() > set.size()) {
					continue;
				}
				if (s.substring(i, j + 1).length() == set.size() && set.size() > max) {
					max = set.size();
				}
			}
		}
		return max;
	}


	/**
	 * 游标下滑
	 * @param s
	 * @return
	 */
	static int lengthOfLongestSubstring3(String s) {
		int maxLen = 0;
		int start = 0, end = 0;
		for (; end < s.length(); end++) {
			int indexOf = s.substring(start, end).indexOf(s.charAt(end));
			if (indexOf != -1) {
				maxLen = Math.max(maxLen, end - start);
				start += indexOf + 1;
			}
		}
		return Math.max(maxLen, end - start);
	}
}
